package com.peng.leetcode.swordoffer;

/**
 * SwordFindNumberIn2DArray
 * 剑指 Offer 04. 二维数组中的查找
 * https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
 *
 * @author: lupeng6
 * @create: 2023/3/10 12:05
 */
public class SwordFindNumberIn2DArray {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        for (int i = 0; i < matrix.length; i++) {
            int[] arr = matrix[i];
            if (arr.length > 0 && arr[0] <= target && target <= arr[arr.length - 1]) {
                int l = 0;
                int r = arr.length - 1;
                while (l <= r) {
                    int mid = l + (r - l) / 2;
                    if (arr[mid] == target) {
                        return true;
                    }
                    if (arr[mid] < target) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
            }
        }
        return false;
    }
}
